package AVLTests;


public class BinTree {
	private Root head;
	private Root current;
	String serialization;
	private int i=0;
	private int h_max=5;
	BinTree(){head=new Root();i=0;}
	private void resetSerialization(){serialization="";}
	public void sethead(Root head) {this.head=head;}
	public Root gethead(){return head;}
	public void setcurrent(Root current){this.current=current;}
	public Root getcurrent(){return current;}
	public Root create(char[] s, Root cur) //создать дерево по скобочному представлению
	{
		while(s[i]!='(' && s[i]!='\0')
			i++; //Доходим до скобки перед символом
		if(s[i]=='(') 
		{
			cur.seta(s[i+1]); //читать символ
			if(s[i+2]=='(') //если не атом
			{
				Root leftson=new Root();
				cur.setLeft(leftson);		
				i++;
				create(s,leftson); 
			
				Root rightson=new Root();
				cur.setRight(rightson);   
				i++;				
				create(s,rightson);
			}
			else 
			{
				cur.setLeft(null);   
				cur.setRight(null);  
				i++;			
				return (cur);
			}
		}
		else 
		{
			i++;              
			return (cur);
		}
		return (cur);
	}
		
	public Root generate(int err_tree) //генерация дерева
	{
		if(err_tree>=h_max)	//если достигли макс высоты
		{
			return null;
		}
		err_tree++;
	    double r=Math.random()*100;			
	     if(r<31)			
			return null;
		else				
		{
			Root cur=new Root();
			r=Math.random()*26;
			cur.seta((char)(0x61+(int)r));		
			cur.setLeft(generate(err_tree));  
			cur.setRight(generate(err_tree)); 
			return cur;
		}
	}
	
	public int tree_h(Root cur) //находит высоту дерева
	{
		int h1=0,h2=0;
		if(cur==null) return 0;
		if(!isAtom(cur))   
		{
			if(cur.getLeft()!=null) h1=tree_h(cur.getLeft()); //находим высоту левого поддерева
			if(cur.getRight()!=null) h2=tree_h(cur.getRight()); //находим высоту правого поддерева
			if(h1>h2)
				return h1+1;
			else 
				return h2+1;
		}
		else
		{
			return 1; 
		}
	}
	
	public void check_balance(Root cur) //подсчет разностей hr-hl
	{
		if(cur!=null) 
		{
			cur.setb(tree_h(cur.getRight())-tree_h(cur.getLeft())); 
			check_balance(cur.getLeft()); 
			check_balance(cur.getRight()); 
		}
	}
	
	public boolean check_avl(Root cur) //является ли дерево AVL
	{
		if(cur==null) 
			return false;
		boolean res,resl=true,resr=true;
		int hl=0,hr=0;
		if(cur.getLeft()!=null) 
		{
			resl=check_avl(cur.getLeft());
		}
		if(cur.getRight()!=null) 
		{
			resr=check_avl(cur.getRight());
		}
		if(!(resr && resl)) 
			return false;
		hl=tree_h(cur.getLeft()); 
		hr=tree_h(cur.getRight());	
		res = (Math.abs(hl-hr)<2); 
		return res;
	}
	
	public Root pov_l(Root cur)//поворот влево
	{
		Root save,nh=cur;
		if(!isAtom(cur) && cur.getRight()!=null)
		{
			nh=cur.getRight();
			save=nh.getLeft();
			nh.setLeft(cur);
			cur.setRight(save);
		}
		return nh;
	}
	
	public Root pov_r(Root cur)//поворот вправо
	{
		Root save,nh=cur;
		if(!isAtom(head) && cur.getLeft()!=null)
		{
			nh=cur.getLeft();
			save=nh.getRight();
			nh.setRight(cur);
			cur.setLeft(save);
		}
		return nh;
	}
	
	public Root tree_change(Root cur) //переделать дерево в AVL
	{
		if(cur==null) return cur;
		if(cur.getLeft()!=null)						
			cur.setLeft(tree_change(cur.getLeft()));     
		if(cur.getRight()!=null)						
			cur.setRight(tree_change(cur.getRight()));	
		check_balance(cur);                     
		if(!check_avl(cur))						
		{
			if(cur.getb()<-1 && cur.getLeft().getb()>0)       
			{
				cur.setLeft(pov_l(cur.getLeft()));		
				cur=pov_r(cur);				
				check_balance(cur);				
				return cur;
			}
			if(cur.getb()<-1 && cur.getLeft().getb()<=0)		
			{
				cur=pov_r(cur);				
				check_balance(cur);				
				return cur;
			}
			if(cur.getb()>1 && cur.getRight().getb()<0)		
			{
				cur.setRight(pov_r(cur.getRight()));		
				cur=pov_l(cur);					
				check_balance(cur);				
				return cur;
			}
			if(cur.getb()>1 && cur.getRight().getb()>=0)		
			{
				cur=pov_l(cur);					
				check_balance(cur);				
				return cur;
			}
		}
		return cur;
	}
	
	public void add_elem(Root cur,char s) //добавить элемент в сторону l или r
	{
		if(cur.getLeft()==null && s=='l')
		{
			Root nr=new Root();
			
			//cur.Left=new Root();
			double r=Math.random()*26;
			nr.seta((char)(0x61+(int)r));
			cur.setLeft(nr);
		}
		if(cur.getRight()==null && s=='r')
		{
			Root nr=new Root();
			
			double r=Math.random()*26;
			nr.seta((char)(0x61+(int)r));
			cur.setRight(nr);
		}
		check_balance(head);
	}
	
	public Root del_elem(Root hd, Root cur) //удалить элемент
	{
		if(cur==null) return hd;
		if(hd!=null)  
		{
			h_del(hd,cur);
			if(hd==cur)
			{
				return null;
			}
			check_balance(hd);
		}
		else 
		{
			return null;
		}
		return hd;
	}
	
	void h_del(Root hd,Root cur) //установка указателя на уделяемый элемент null
	{
		if(cur==hd) return;
		if(hd!=null)  
		{
			if(hd.getLeft()==cur || hd.getRight()==cur) 
			{
				if(hd.getLeft()==cur)  
					hd.setLeft(null);
				else				
					hd.setRight(null);
			}
			else
			{
				h_del(hd.getLeft(),cur); 
				h_del(hd.getRight(),cur);
			}
		}
	}
	
	boolean isAtom(Root s) //проверка на атом
	{
		if(s==null) return false;
		else return ((s.getLeft()==null) && (s.getRight()==null));
	}
		
	public void out_lst(Root cur) //вывод на экран
	{
		if(cur!=null)
		{
			if(!isAtom(cur))    
			{
				System.out.print("("+cur.geta());
				if(cur.getLeft()!=null)
					out_lst(cur.getLeft());
				else
					System.out.print("($)");
				if(cur.getRight()!=null)
					out_lst(cur.getRight()); 
				else
					System.out.print("($)");
				System.out.print(")");
			}
			if(isAtom(cur))
			{
				System.out.print("("+cur.geta()+")"); 
			}
		}
		else System.out.print("\nПустое дерево!\n");
	}
	
	private void Serialization(Root cur) //сериализация
	{
		if(cur!=null)
		{
			if(!isAtom(cur))    
			{
				serialization+=("("+cur.geta());
				if(cur.getLeft()!=null)
					Serialization(cur.getLeft());
				else
					serialization+=("($)");
				if(cur.getRight()!=null)
					Serialization(cur.getRight()); 
				else
					serialization+=("($)");
				serialization+=(")");
			}
			if(isAtom(cur))
			{
				serialization+=("("+cur.geta()+")"); 
			}
		}
		else serialization+=("\nПустое дерево!\n");
	}
	
	public String getSerialization()
	{
		this.resetSerialization();
		this.Serialization(head);
		return serialization;
	}
	
	public Root chose_bt(Root crt,char[] s) //выбор корня дерева
	{
		i=0;
		Root cur;
		cur=crt;
		while(s[i]!='s' && i<s.length) 
		{
			switch(s[i])
			{
				case 'l':
				{
					cur=cur.getLeft();  
					break;
				}
				case 'r':
				{
					cur=cur.getRight(); 
					break;
				}
				case 's':
				{
					return cur;
				}
				default:
				{
					return null;
				}
			}
			if(cur==null)
			{
				return null;
			}
			i++;
		}
		return cur;
	}

	public void delete_empty(Root cur)  //удалить элементы, помеченные как пустые
	{
		if(cur==null) return;
		if(cur.getLeft()!=null) 
		{
			if(cur.getLeft().geta()=='$')
			{
				cur.setLeft(null); 
			}
			else delete_empty(cur.getLeft()); 
		}
		if(cur.getRight()!=null)  
		{
			if(cur.getRight().geta()=='$')
			{
				cur.setRight(null);
			}
			else delete_empty(cur.getRight()); 
		}
	}
}
